
package arbre;

import java.util.Collection;

/**
 * Représente le noeud d'un arbre binaire.
 * 
 * @author David Bernard
 * @since java 1.6
 *
 * @param <E> le type de l'élément contenu.
 */
public class NoeudArbreBinaire<E extends Comparable<E>>
{
	private E element = null;
	private NoeudArbreBinaire<E> gauche = null;
	private NoeudArbreBinaire<E> droite = null;

	/**
	 * Construit un noeud avec l'élément désiré.
	 * 
	 * @param element
	 */
	public NoeudArbreBinaire(E element)
	{
		boolean ok = this.setElement(element);

		if (!ok)
		{
			throw new NullPointerException();
		}
	}

	/**
	 * Mutateur de l'élément.
	 * 
	 * @param element un élément non null désirer.
	 * 
	 * @return vrai si la mutation est effectuer.
	 */
	public boolean setElement(E element)
	{
		boolean ok = element != null;
		if (ok)
		{
			this.element = element;
		}

		return ok;
	}

	/**
	 * Donne l'élément contenu dans le noeud
	 * 
	 * @return le contenu du noeud.
	 */
	public E getElement()
	{
		return this.element;
	}
	
	/**
	 * Donne le noeud gauche du noeud.
	 * 
	 * @return le noeud gauche du noeud.
	 */
	public NoeudArbreBinaire<E> getGauche()
	{
		return this.gauche;
	}
	
	/**
	 * Donne le noeud droite du noeud.
	 * 
	 * @return le noeud droite du noeud.
	 */
	public NoeudArbreBinaire<E> getDroite()
	{
		return this.droite;
	}
	
	/**
	 * Set le noeud gauche.
	 * 
	 * @param gauche le noeud gauche.
	 */
	public void setGauche(NoeudArbreBinaire<E> gauche)
	{
		this.gauche = gauche;
	}
	
	/**
	 * Set le noeud droite.
	 * 
	 * @param droite le noeud droite.
	 */
	public void setDroite(NoeudArbreBinaire<E> droite)
	{
		this.droite = droite;
	}
	
	@Override
	public String toString()
	{
		return this.element.toString();
	}
	
	 void set(E element)
	{
		this.push(element, true);
	}
	
	 void add(E element)
	{
		this.push(element, false);
	}
	
	 E get(E cle)
	{
		E out = null;
		int diff = this.element.compareTo(cle);

		if ((this.droite != null) && (diff < 0))
		{
			out = this.droite.get(cle);
		}
		else if ((this.gauche != null) && (diff > 0))
		{
			out = this.gauche.get(cle);
		}
		else if (diff == 0)
		{
			out = this.getElement();
		}

		return out;
	}
	
	 int size()
	{
		int nbFils = 1;

		if (this.gauche != null)
		{
			nbFils += this.gauche.size();
		}

		if (this.droite != null)
		{
			nbFils += this.droite.size();
		}

		return nbFils;
	}
	
	 void addToList(Collection<E> list)
	{
		if (this.gauche != null)
		{
			this.gauche.addToList(list);
		}

		list.add(this.element);

		if (this.droite != null)
		{
			this.droite.addToList(list);
		}
	}
	
	void printValues()
	{
		this.printValues("");
	}
	
	int degree()
	{
		int degreeG = 0;
		int degreeD = 0;

		if (this.gauche != null)
		{
			degreeG = this.gauche.degree();
		}

		if (this.droite != null)
		{
			degreeD = this.droite.degree();
		}

		return 1 + Math.max(degreeG, degreeD);
	}
	
	private void push(E element, boolean acceptDupl)
	{
		int diff = this.element.compareTo(element);
		if (diff < 0)
		{
			if (this.droite == null)
			{
				this.droite = new NoeudArbreBinaire<E>(element);
			}
			else
			{
				this.droite.push(element, acceptDupl);
			}
		}
		else if (diff > 0)
		{
			if (this.gauche == null)
			{
				this.gauche = new NoeudArbreBinaire<E>(element);
			}
			else
			{
				this.gauche.push(element, acceptDupl);
			}
		}
		else if (acceptDupl)
		{
			this.element = element;
		}
		else
		{
			throw new DuplicateItemException();
		}
	}
	
	private void printValues(String tab)
	{
		System.out.println(tab + " " + this.element.toString());

		if (this.gauche != null)
		{
			this.gauche.printValues(tab + "G");
		}

		if (this.droite != null)
		{
			this.droite.printValues(tab + "D");
		}
	}
}
